import org.junit.Test;

import javax.security.auth.kerberos.KerberosTicket;
import java.util.ArrayList;
import java.util.List;

public class Solution42 {
    /**
     * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
     * 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
     * 示例:
     * <p>
     * 输入: [0,1,0,2,1,0,1,3,2,1,2,1]
     * 输出: 6
     */
    @Test
    public void test() {
        System.out.println(trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
    }

    public int trap(int[] height) {
        int maxIndex = 0, max = 0;
        for (int i = 0; i < height.length; i++) {
            if (height[i] >= max) {
                max = height[i];
                maxIndex = i;
            }
        }
        int area = 0;
        int i = 0, j = i + 1;
        while (j < maxIndex) {
            while (j < maxIndex && height[j] < height[i]) {
                j++;
            }
            int localArea = height[i] * (j - i);
            for (int k = i; k < j; k++) {
                localArea -= height[k];
            }
            area += localArea;
            i = j;
            j = i + 1;

        }
        i = height.length - 1;
        j = i - 1;
        while (j > maxIndex) {
            while (j > maxIndex && height[j] < height[i]) {
                j--;
            }
            int localArea = height[i] * (i - j);
            for (int k = i; k > j; k--) {
                localArea -= height[k];
            }
            area += localArea;
            i = j;
            j = i - 1;
        }
        return area;
    }
}
